package leetcode;

import java.util.Arrays;

public class LongestSubstringKtimes {

	public static void main(String[] args) {
		LongestSubstringKtimes object = new LongestSubstringKtimes();
		String string = "abbbbbbcaa";
		int k = 3;
		System.out.println(object.longestSubstring(string, k));
	}
	
	//Find the length of the longest substring T of a given string (consists of lowercase letters only)
	// such that every character in T appears no less than k times.
    
	//本来以为这样很慢，没想到意外的beat 83.43%
	public int longestSubstring(String s, int k) {
        if(s == null){
        	return 0;
        }
        int length = s.length();
        if(length <= 0){
        	return 0;
        }
        int[] map = new int[26];
        for(int i = 0; i < length; i++){
        	map[s.charAt(i) - 'a']++;
        }
        
        int[] cur = new int[26];
        StringBuilder sb = new StringBuilder();
        int res = 0;
        for(int i = 0; i < length; i++){
        	char c = s.charAt(i);
        	if(map[c - 'a'] >= k){
        		sb.append(c);
        	}else{
        		//遇到出现次数小于k的字符
        		//首先判断sb是否是满足条件的
        		res = Math.max(res, isReal(sb, cur, k));
        	}
        }
        System.out.println(s + " " + sb);
        //在结尾处还需要再判断一次
        res = Math.max(res, isReal(sb, cur, k));
        System.out.println(s + " res: " + res);
        return res;
    }
	
	public int isReal(StringBuilder sb, int[] cur, int k){
		int res = 0;
		int curLength = sb.length();
		if(curLength < k){
			sb.delete(0, curLength);
			return 0;
		}
		for(int j = 0; j < curLength; j++){
			cur[sb.charAt(j) - 'a']++;
        }
		//标志是否所出现的字符所有的都大于等于k
		boolean flag = true;
		boolean hasMoreThanK = false;
		for(int j = 0; j < 26; j++){
			if(cur[j] != 0 && cur[j] < k){
				flag = false;
				//break;
			}else if(cur[j] >= k){
				hasMoreThanK = true;
			}
		}
		if(flag){
			res = curLength;
		}else if(hasMoreThanK){
			//这是一个递归的的过程，返回sb最长的substring
			System.out.println("is true: " + sb.toString());
			res = longestSubstring(sb.toString(), k);
		}
		System.out.println("sb: " + sb + " k: " + k + "  " + res );
		Arrays.fill(cur, 0);
		sb.delete(0, curLength);
		return res;
	}
}
